// 1. 爬楼梯
pub fn climb_stairs(n: usize) -> u32 {
    if n == 1 {
        return 1;
    }
    let mut dp = vec![0; n];
    dp[0] = 1;
    dp[1] = 2;
    for i in 2..n {
        dp[i] = dp[i - 2] + dp[i - 1];
    }
    dp[n - 1]
}

// 2. 最大子序和
pub fn max_sub_array(nums: Vec<i32>) -> i32 {
    if nums.len() < 1 {
        return 0;
    }
    let mut dp = vec![0; nums.len()];
    dp[0] = nums[0];
    for i in 1..nums.len() {
        dp[i] = i32::max(nums[i], dp[i - 1] + nums[i]);
    }
    *dp.iter().max().unwrap()
}

// 3. 最长上升子序列
pub fn length_of_list(nums: Vec<i32>) -> i32 {
    if nums.len() < 1 {
        return 0;
    }
    let mut dp = vec![0; nums.len()];
    for i in 0..nums.len() {
        dp[i] = 1;
        for j in 0..i {
            if nums[j] < nums[i] {
                dp[i] = i32::max(dp[j] + 1, dp[i]);
            }
        }
    }
    *dp.iter().max().unwrap()
}

// 4. 三角形最小路径和
pub fn mini_mum_total(triangle: Vec<Vec<i32>>) -> i32 {
    if triangle.len() < 1 {
        return 0;
    }
    let mut dp = vec![0; triangle[0].len()];
    dp[0] = triangle[0][0];
    dp[1] = triangle[1][1] + dp[0];
    dp[0] = triangle[1][0] + dp[0];
    for i in 2..triangle.len() {
        dp[i] = triangle[i][i] + dp[i - 1];
        for j in (1..i).rev() {
            dp[j] = triangle[i][j] + i32::min(dp[j], dp[j - 1]);
        }
        dp[0] = triangle[i][0] + dp[0];
    }
    *dp.iter().min().unwrap()
}
// 4.2 矩阵最小路径和
pub fn min_path_sum(grid: &mut Vec<Vec<i32>>) -> i32 {
    if grid.len() < 1 {
        return 0;
    }
    for i in 1..grid[0].len() {
        grid[0][i] = grid[0][i-1] + grid[0][i];
    }
    for i in 1..grid.len() {
        grid[i][0] = grid[i-1][0] + grid[i][0];
        for j in 1..grid[0].len() {
            grid[i][j] = grid[i][j] + i32::min(grid[i][j-1], grid[i-1][j]);
        }
    }
    grid[grid.len()-1][grid[0].len()-1]
}

// 5. 打家劫舍
pub fn rob(nums: &mut Vec<i32>) -> i32 {
    if nums.len() < 1 {
        return 0;
    }
    if nums.len() < 2 {
        return nums[0];
    }
    if nums.len() < 3 {
        return i32::max(nums[0], nums[1]);
    }
    for i in 2..nums.len() {
        nums[i] = i32::max(nums[i-2]+nums[i], nums[i-1]);
    }
    *nums.last().unwrap()
}
